Cầu được chính quyền thực dân Pháp cho xây dựng từ năm 1897 đến năm 1899 khi nhận thấy vị trí quan trọng của con đường Hà Nội – Lạng Sơn, Đồng Đăng. Trong chiến tranh biên giới năm 1979, cầu bị phá hủy hoàn toàn.[1]

Năm 1985, tỉnh Lạng Sơn cho xây dựng lại cầu mới với nhịp dầm thép chịu lực nhưng khi sắp hoàn thành thì trận lũ năm 1986 đã cuốn trôi dầm cầu đang thi công. Sau đó, cầu tiếp tục được xây dựng lại theo nguyên mẫu cũ của cầu Kỳ Cùng cũ. Cầu mới được khánh thành năm 1987 và mang tên cầu Kỳ Lừa, gồm 2 nhịp dài 46 m, rộng 9,8 m, hai đầu cầu và đường dẫn được nâng cao hơn 2 m để chống lũ lụt.[1][3]

Sau một thời gian dài sử dụng, cầu có biểu hiện xuống cấp. Khổ cầu hẹp, tải trọng chỉ 10 tấn nên thường xuyên bị ách tắc giao thông trong giờ cao điểm. Trước thực trạng này, ngày 21 tháng 9 năm 2016, UBND tỉnh Lạng Sơn đã ra Quyết định số 1689/QĐ-UBND về việc phê duyệt dự án đầu tư xây dựng cầu mới và được đặt tên lại là cầu Kỳ Cùng.[3]

Ngày 27 tháng 10 năm 2016, cầu Kỳ Cùng mới được khởi công xây dựng với tổng vốn đầu tư là 405 tỷ đồng, do Ban Quản lý dự án đầu tư xây dựng các công trình giao thông, Sở Giao thông Vận tải làm chủ đầu tư. Cầu mới được xây dựng vĩnh cửu, thiết kế theo mô hình cầu vòm bê tông cốt thép dạng hộp, chạy trên, dài 117,2 m với một nhịp, bề rộng 21 m với bốn làn xe và thấp hơn cầu cũ 1,8 m[1][4]. Cầu được thông xe kỹ thuật vào ngày 30 tháng 11 năm 2018.[2]